package q1944_canSeePersonsCount;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Solution {
    public static void main(String[] args) {
        int[] a = {5,4,3,2,1 };
        System.out.println(Arrays.toString(new Solution().canSeePersonsCount(a)));
    }

    /**
     * 注意这道题的题意是 ： 返回一个长度为 n 的数组 answer ，
     * 其中 answer[i] 是第 i 个人在他 右侧队列中 能 看到 的 人数
     * 所以最后一个人是一个人都看不到的
     * 如果有一道题需要我们求他两端能够看到的人数，那么就是反过来再求一次单调栈
     */
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        int[] ans = new int[n];
        // 单调递减栈，保存右边的可能看到的人的下标值
        Deque<Integer> monotoneStack = new ArrayDeque<>();
        // 倒序遍历 能看到多少只与右边的数值有关系
        for (int i = n - 1; i >= 0; i--) {
            while (!monotoneStack.isEmpty()) {
                ans[i]++;
                // 比单调栈中当前值小，证明看不到这个值右边的了，结束比较
                if (heights[i] <= heights[monotoneStack.peek()]) {
                    break;
                }
                // 比单调栈中的当前值大，左边的人肯定都看不到这个值之后的人了
                // 出栈，接着循环
                monotoneStack.pop();
            }
            // 单调栈中放入下标，保证单调递减（栈为空或者h[i]<h[j]）
            monotoneStack.push(i);
        }
        return ans;
    }
}
